package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import java.util.Arrays;
import java.util.regex.Pattern;

/**
 * @author Fengkai
 * @creat 2023/4/23
 * 某农场主管理了一大片果园，fields[i]表示不同果林的面积，单位：（m 2 m^2m
 * 2
 * ），现在要为所有的果林施肥且必须在 n 天之内完成，否则影响收成。
 * 小布是果林的工作人员，他每次选择一片果林进行施肥，且一片果林施肥完后当天不再进行施肥作业。
 * 假设施肥机的能效为 k，单位：（m 2 m^2m
 * 2
 * /day），请问至少租赁能效 k 为多少的施肥机才能确保不影响收成？
 * 如果无法完成施肥任务，则返回-1。
 * 输入
 * 第一行输入为m和n，m表示fields中的元素个数，n表示施肥任务必须在n天内（含n天）完成；
 * 第二行输入为fields，fields[i]表示果林i的面积，单位：（m 2 m^2m2）
 * 输出描述
 * 对于每组数据，输出最小施肥机的能效（k），无多余空格。
 */
public class ShiFei {
    //二分
    public static void main (String[] args) {
        System.out.println(shiFei(new int[]{5, 7, 9, 15, 10}, 7));
    }

    public static int shiFei (int[] fields, int n) {
        Arrays.sort(fields);
        int length = fields.length;
        if (length > n) {
            return -1;
        }
        if (length == n) {
            return fields[length - 1];
        }
        int left = 0;
        int result = 0;
        int right = fields[length - 1];
        while (left + 1 < right) {
            int mid = (int) Math.ceil((double) (left + right) / 2);
            int days = 0;
            for (int i = 0; i < length; i++) {
                int day = (int) Math.ceil((double) fields[i] / mid);
                days += day;
            }
            if (days > n) {
                left = mid;
            } else {
                result = mid;
                right = mid;
            }
        }
        return result;
    }
}
